package com.problem.leetcode;

import java.util.Arrays;

/**
 * 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
 * <p>
 * 例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
 * <p>
 * 与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/3sum-closest
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * <p>
 * 解题思路:还是有三个指针，首先给数组排序，比较绝对值，绝对值与target最接近的就是返回值，指针的移动条件就是如果当前值<目标值，左指针右移动，反之，右指针左移
 */
public class Problem16 {
    public int threeSumClosest(int[] nums, int target) {

        Arrays.sort(nums);
        int result = 0;
        result = nums[0] + nums[1] + nums[nums.length - 1];

        for (int i = 0; i < nums.length - 1; i++) {
            int left = i + 1, right = nums.length - 1;
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            while (left < right) {
                int cur = nums[i] + nums[left] + nums[right];
                if (cur == target) {
                    return target;
                }

                if (Math.abs(cur - target) < Math.abs(result - target)) {
                    result = cur;
                }

                if (cur < target) {
                    ++left;
                }
                if (cur > target) {
                    --right;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Problem16 problem16 = new Problem16();
        int[]     array     = new int[]{1, 1, 1, 0};
        // int       result    = problem16.threeSumClosest(array, 100);

        // array = new int[]{0, 2, 1, -3};
        // int result = problem16.threeSumClosest(array, 1);

        array = new int[]{-1,2,1,-4};
        int result = problem16.threeSumClosest(array, 1);

        System.out.println(result);
    }

}
